/**
 * @file
 * Operations on lists.
 */

#ifndef LIST_OPS_H
#define LIST_OPS_H

#include <set>
#include <map>
#include <list>

/**
 * Partition a list of objects into sets such that members of each set are equivalent.
 * Note that the comparison functor is expected to be implemented for the objects.
 * @param[in] given The give list of objects.
 * @param[out] result The partitioned set of sets of objects.
 * @param[in] comparison The comparison functor.
 */
template<class T, class F>
  void partition(std::list<T*> *given, std::set<std::set<T*> > *result, F comparison)
{
  // Temporary storage for result, a map from a distinct element to the set of elements
  // such that each element in the set is equal to all other elements in the set
  std::map<T*, std::set<T*> > temp;

  // Iterate over the given list of elements
  for(typename std::list<T*>::iterator i = given->begin();
      i != given->end();
      i++)
    {
      // Condition where the temporary storage is empty, on first element 
      if (temp.size() == 0)
        {
          // Initialize the temporary storage with the first element
          std::set<T*> curr;
          curr.insert(*i);
          temp.insert(std::pair<T*, std::set<T*> >(*i, curr));
        }
      else
        { 
          // Flag indicating that a match was found in the temporary storage
          bool found = false;
          
          // Iterate over the temporary storage
          for(typename std::map<T*, std::set<T*> >::iterator j = temp.begin();
              j != temp.end();
              j++)            
            // Check if there is a match
            if (comparison(*i, j->first))
              {
                // Insert the element in the temporary storage
                (j->second).insert(*i);
                found = true;
                break;
              }
          // Condition where a match was not found
          if (! found)
            {
              // Initialize the current element in the temporary storage
              std::set<T*> curr;
              curr.insert(*i);
              temp.insert(std::pair<T*, std::set<T*> >(*i, curr));
            }
        }
    }

  // Copy the temporary storage into the result
  for(typename std::map<T*, std::set<T*> >::iterator j = temp.begin();
      j != temp.end();
      j++)
    result->insert(j->second);
}
/**
 * Expand a list objects.
 * Note that the expansion functor is expected to be implemented for the objects.
 * @param[in] given The give list of objects.
 * @param[out] result The expanded list of objects.
 * @param[in] expand The expansion functor.
 */
template<class T, class F>
  void expand(std::list<T*> *given, std::list<T*> *result, F expand)
{
  // Iterate over the given list
  for(typename std::list<T*>::iterator i = given->begin();
      i != given->end();
      i++)
    {
      // Expand the current object
      std::list<T*> curr_result;
      expand(*i, &curr_result);

      // Iterate over the current result list
      for(typename std::list<T*>::iterator j = curr_result.begin();
          j != curr_result.end();
          j++)
        // Add the current result element to final result list
        result->push_back(*j);
      
      // Clear the current result list
      curr_result.erase(curr_result.begin(), curr_result.end());
    }
}

/**
 * Delete equivalent objects from a list of objects.
 * Note that the comparison functor is expected to be implemented for the objects.
 * @param[in] given The give list of objects.
 * @param[out] result The list of objects with equivalent objects deleted.
 * @param[in] comparison The comparison functor.
 */
template<class T, class F>
  void delete_identical(std::list<T*> *given, 
                        std::list<T*> *result,
                        std::list<T*> *identical,
                        F comparison)
{
  // Iterate over the given list
  for(typename std::list<T*>::iterator i = given->begin();
      i != given->end();
      i++)
    {
      // Flag indicating that a match has been found
      bool found = false;
      
      // Iterate over the result list
      for(typename std::list<T*>::iterator j = result->begin();
          j != result->end();
          j++)
        // Check if there is a match
        if(comparison(*i,*j))
          found = true;
      
      // If there is no match add the object to the result list
      if (! found)
        result->push_back(*i);
      else
        identical->push_back(*i);
    }
}

#endif // LIST_OPS_H
